package puzzle.projecteuler.p100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Problem088C {

	
	private static Map<Integer, List<List<Integer>>> cache = new HashMap<Integer, List<List<Integer>>>();
	/**
	 * N = x1 + ... + xk = x1 * ... * xk
	 * 容易得到如下性质：
	 * 1) k < N <= 2k
	 * 2) max(x1, ..., xk) <= k
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		Set<Integer> set = new HashSet<Integer>();
		for (int k = 2; k <= 12000; k ++) {
			set.add(n(k));
		}
		int sum = 0;
		for (Integer a: set) {
			sum += a;
		}
		System.out.println(sum);
		System.out.println((System.currentTimeMillis() - s) + " ms");
	}
	
	/**
	 * 返回满足条件的最小N
	 * @param k
	 * @return
	 */
	public static int n(int k) {
		
		for (int N = k+1; N < 2*k; N ++) {
			if (check(N, k)) {
				return N;
			}
		}
		return 2*k;
	}

	/**
	 * 测试n能否满足条件
	 * @param n
	 * @param k
	 * @return
	 */
	private static boolean check(int n, int k) {
		
		List<List<Integer>> fs = factors(n);
		for (List<Integer> f : fs) {
			int sum = k-f.size();
			for (Integer a: f) {
				sum += a;
			}
			if (sum == n) {
				return true;
			} else {
				continue;
			}
		}
		return false;
	}

	/**
	 * 将n分解为若干>1的数乘积的所有方法。
	 * 为了提高效率，这里加了cache
	 * @param n
	 * @return
	 */
	private static List<List<Integer>> factors(int n) {
		
		if (cache.get(n) != null) {
			return cache.get(n);
		} else {
			List<List<Integer>> rs = new ArrayList<List<Integer>>();
			if (n == 1) {
				List<Integer> tmp = new ArrayList<Integer>();
				rs.add(tmp);
			} else {
				for (int f = 2; f <= n; f ++) {
					if (n%f == 0) {
						List<List<Integer>> tmp = factors(n/f);
						for (List<Integer> l: tmp) {
							//为了减少重复数据，限制所有的乘数必须按降序排列
							boolean g = true;
							for (Integer a: l) {
								if (a > f) {
									g = false;
									break;
								}
							}
							if (g) {
								List<Integer> newl = new ArrayList<Integer>();
								for (Integer a: l) {
									newl.add(a);
								}
								newl.add(f);
								rs.add(newl);
							}
						}
					}
				}
			}
			cache.put(n, rs);
			return rs;
		}
	}
}
